package GreedyAlgorithms;

import javax.swing.plaf.basic.BasicInternalFrameTitlePane;
import java.sql.Connection;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

/**
 * 盛最多水的容器
 */
public class P11 {
    public static void main(String[] args) {
        int[] a = {1, 8, 6, 2, 5, 4, 8, 3, 7};

        P11Test02 p11Test02 = new P11Test02();
        System.out.println(p11Test02.maxArea(a));
    }
}

class P11Test01 {
    //下标排序
    private Integer[] sortIndex;

    public int maxArea(int[] height) {
        if (height.length == 2)
            return Math.min(height[0], height[1]);
        int length = height.length;
        sortIndex = new Integer[length];
        for (int i = 0; i < length; i++) {
            sortIndex[i] = i;
        }
        //逆序排序
        Arrays.sort(sortIndex, Comparator.comparingInt(i -> -height[i]));
        //找最大的答案
        int maxNum = Integer.MIN_VALUE;

        //遍历排序后的下标，这就是排好序的数组,利用foreach，不用也行
        for (int i = 1; i < length; i++) {
            for (int j = 0; j < i; j++) {
                int area = Math.abs(sortIndex[i] - sortIndex[j]) * Math.min(height[sortIndex[i]], height[sortIndex[j]]);
                if (maxNum > area)
                    return maxNum;
                maxNum = Math.max(maxNum, area);
            }
        }

        return maxNum;


    }
}

/**
 * 双指针法,设计使用两个维度时，可以考虑双指针，这样有效降低复杂度
 */
class P11Test02 {

    public int maxArea1(int[] height) {
        if (height.length == 2)
            return Math.min(height[0], height[1]);

        int len = height.length;

        int l = 0, r = len - 1;
        int maxNum = Integer.MIN_VALUE;
        while (l < r) {
            int x = r - l;
            int y = Math.min(height[l], height[r]);
            maxNum = Math.max(maxNum, x * y);

            if (height[l] > height[r]) {
                r--;
            } else {
                l++;
            }
        }

        return maxNum;

    }


    public int maxArea(int[] height) {
        int l = 0;
        int r = height.length - 1;
        int max = 0;
        while (l < r) {
            int t;
            if (height[l] > height[r]) {
                t = height[r] * height[r];
                r--;
            } else {
                t = height[l] * height[l];
                l++;
            }
            if (t > max) {
                max = t;
            }
        }

        return max;
    }
}
